package basic.study.leetcode;

/**
 * @ClassName Mid05
 * @Description 从前序与中序遍历序列构造二叉树
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/26 9:38
 * @Version 1.0
 */
public class Mid105 {
    class Solution {
        int[] pre;
        int[] in;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            pre = preorder;
            in = inorder;
            int inStart = 0;
            int inEnd = inorder.length-1;
            int preStart = 0;
            int preEnd = preorder.length-1;

            return build(preStart, preEnd, inStart, inEnd);
        }

        public TreeNode build(int preStart, int preEnd, int inStart, int inEnd) {
            if (preStart > preEnd || inStart > inEnd) {
                return null;
            }
            //根节点
            TreeNode root = new TreeNode(pre[preStart]);
            //左右子节点数
            int index = findIndexOfVal(in, pre[preStart]);
            int leftNum = index - inStart;
            int rightNum = inEnd - index;
            if (leftNum > 0) {
                root.left = build(preStart+1, preStart+leftNum, inStart, index-1);
            }
            if (rightNum > 0) {
                root.right = build(preStart+leftNum+1, preEnd, index+1, inEnd);
            }
            return root;
        }

        public int findIndexOfVal(int[]arr, int val) {
            int index = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == val) {
                    index = i;
                    break;
                }
            }
            return index;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
